Search for: All records

Equivalence of deterministic finite automata (DFAs) has been researched for several decades, but equivalence of nondeterministic finite automata (NFAs) is not as studied. Equivalence of two NFAs is a PSPACE-complete problem. NFA equivalence is a challenging theoretical problem with practical applications such as lexical analysis. Quantified boolean formulas (QBFs) naturally encode PSPACE-complete problems, and we share our preliminary work towards determining NFA equivalence via QBFs. 

Abstract The Breakthrough Listen Initiative is conducting a program using multiple telescopes around the world to search for “technosignatures”: artificial transmitters of extraterrestrial origin from beyond our solar system. The Very Energetic Radiation Imaging Telescope Array System (VERITAS) Collaboration joined this program in 2018 and provides the capability to search for one particular technosignature: optical pulses of a few nanoseconds in duration detectable over interstellar distances. We report here on the analysis and results of dedicated VERITAS observations of Breakthrough Listen targets conducted in 2019 and 2020 and of archival VERITAS data collected since 2012. Thirty hours of dedicated observations of 136 targets and 249 archival observations of 140 targets were analyzed and did not reveal any signals consistent with a technosignature. The results are used to place limits on the fraction of stars hosting transmitting civilizations. We also discuss the minimum pulse sensitivity of our observations and present VERITAS observations of CALIOP: a space-based pulsed laser on board the Cloud-Aerosol Lidar and Infrared Pathfinder Satellite Observations. The detection of these pulses with VERITAS, using the analysis techniques developed for our technosignature search, allows a test of our analysis efficiency and serves as an important proof of principle.